“I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible.” - Carl Friedrich Gauss
Although there are many ways to structure proofs, the “default” (and most common) approach is to have the structure of the proof exactly match the structure of the formula being proved. In this section, we consider common patterns involving proofs for quantified formulas.
By far the most common way to prove an assertion of the form \(\forall x\ P(x)\) is to present a proof that starts by assuming \(x\) is completely arbitrary, and showing that we can prove \(P(x)\). If we can do so with no assumptions about \(x\), then our proof is completely general, the same argument would work for any specific value of \(x\), and so \(\forall x\ P(x)\) holds.
In the more common case of restricted quantifiers like \(\forall x\in S\ \ P(x)\), we use the same idea except we assume we know nothing about \(x\) except that it is an element of \(S\).
As usual, there are many possible choices of wording. Here are several examples of the pattern:
Example
Theorem: \(\forall x\in S\ \ P(x)\)
Proof: Let \(x\in S\) be arbitrary. ⋮ Thus, \(P(x)\).
Theorem: \(\forall x\in S\ \ P(x)\)
Proof: Let \(x\in S\) be given. ⋮ so \(P(x)\).
Theorem: \(\forall x\leq N\ \ P(x)\)
Proof: Assume \(x\leq N\). ⋮ so \(P(x)\).
Theorem: \(\forall x\leq N\ \ P(x)\)
Proof: Let \(x\leq N\) be fixed but arbitrary. ⋮ so \(P(x)\).
The most direct to prove an assertion of the form \(\exists x\ P(x)\) is to find such a value. (Or show that one of several values must work.) Here are several examples of the pattern:
Example
Theorem: \(\exists x\in \mathbb{N}\ \ P(x)\)
Proof: ⋮ Thus, \(P(42)\).
Theorem: \(\exists x\in \mathbb{N}\ \ P(x)\)
Proof: Put \(x = 42\). ⋮ and hence \(P(x)\).
Theorem: \(\exists x\in \mathbb{N}\ \ P(x)\)
Proof: ⋮ Therefore, \(P(42)\) or \(P(47)\).
Many mathematical statements are universally quantified implications. In these cases, we can combine the pattern for proving a universally quantified formula with the pattern for proving an implication.
Example
Theorem: \(\forall x\in S\ \ \bigl(P(x)\to Q(x)\bigr)\) > >Proof: Let \(x\in S\) be arbitrary. >Assume \(P(x)\). >⋮ Thus, \(Q(x)\). > >— > Theorem: \(\forall x\in S\ \ \bigl(P(x)\to Q(x)\bigr)\) > >Proof: Let \(x\in S\) be given such that \(P(x)\). >⋮ Thus, \(Q(x)\).
If a statement corresponds to a formula with multiple quantifiers, we just apply the appropriate patterns for each quantifier in order.
Example
Theorem: \(\forall x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ R(x,y)\) > Proof: Let \(x{\in}\mathbb{N}\) be given. Let \(y = \min\{\lfloor\sqrt{x}\rfloor,10\}\). ⋮ Thus, \(R(x,y)\). > >— > Theorem: \(\exists x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ R(x,y)\) > Proof: Put \(x := \min\{\lfloor\sqrt{x}\rfloor,10\}\). Let \(y{\in}\mathbb{N}\) be given. ⋮ Thus, \(R(x,y)\). > >— > >Theorem: \(\forall x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ R(x,y)\) > >Proof: >Let \(x{\in}\mathbb{N}\) and \(y{\in}\mathbb{N}\) be arbitrary. ⋮ >Thus, \(R(x,y)\). > >— > Theorem: \(\exists x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ R(x,y)\) > Proof: Put \(x{:=}42\) and \(y:=47\). ⋮ Thus, \(R(x,y)\).
Example
Theorem: \(\forall x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ \forall z{\in}\mathbb{N}\ T(x,y,z)\) > Proof: Let \(x{\in}\mathbb{N}\) and \(y{\in}\mathbb{N}\) and \(z{\in}\mathbb{N}\) be given. ⋮ Thus, \(T(x,y,z)\). > >— > Theorem: \(\forall x{\in} \mathbb{N}\ \ \exists y{\in}\mathbb{N} \ \exists z{\in}\mathbb{N}\ T(x,y,z)\) > Proof: Let \(x{\in}\mathbb{N}\) be given. Put \(y := x+1\) and \(z := 2x\). ⋮ Thus, \(T(x,y,z)\). > >— > Theorem: \(\exists x{\in} \mathbb{N}\ \ \forall y{\in}\mathbb{N} \ \exists z{\in}\mathbb{N}\ T(x,y,z)\) > >Proof: >Put \(x{:=}99\). > Let \(y{\in}\mathbb{N}\) be given. > Put \(z := x+y-1\). > ⋮ > Thus, \(T(x,y,z)\).
Common strategies for proving a quantified statement mimic the Introduction rules of Natural Deduction. Similarly, strategies for applying quantified statements already known (or assumed) to be true mimic the Elimination rules of Natural Deduction.
Once we know something is true for all \(x\), we can assert it any specific value(s) of interest.
Example
Proof: Assume \(\forall n{\in}\mathbb{N}\ Q(n)\). Then \(Q(42)\), so … ⋮ > >— > Proof: Assume \(\forall n{\in}\mathbb{N}\ Q(n)\). ⋮ By assumption, \(Q(0)\) and \(Q(1)\), so …
If we know something exists, we can give that thing a name. The name may or may not be the same as the bound variable in our existential; it doesn’t matter except that we may not use a name that we’re not already using to stand for some other specific value. (Also, as in the \(\exists E\) rule, the name we choose for “the thing that exists” should not be a free variable in the conclusion of our proof.)
Example
Proof: Assume \(\exists n{\in}\mathbb{N}\ Q(n)\). Then \(Q(k)\) for some \(k{\in}\mathbb{N}\), so … \(k\) … > >— > Proof: Assume \(\exists n{\in}\mathbb{N}\ Q(n)\). Then \(Q(n)\) for some \(n{\in}\mathbb{N}\), so … \(k\) …
Nested quantifiers work as above; we just handle each quantifier in sequence.
Example
Proof: Assume \(\forall x\in\mathbb{R}\ \forall y\in\mathbb{R}\ \exists z{\in}\mathbb{R}\ \ f(x,z)=g(y)\) . > Then there exist \(z_1{\in}\mathbb{R}\) such that \(f(3,z_1) = g(4)\) and \(z_2{\in}\mathbb{R}\) such that \(f(9, z_2) = g(7)\). ⋮ > Note: Implicit in this proof is that plugging \(3\) in for \(x\) in the assumption gives us >\[ >\forall y\in\mathbb{R}\ \exists z{\in}\mathbb{R}\ f(3,z)=g(y). >\] >Plugging \(4\) in for \(y\) in that statement gives us >\[ >\exists z{\in}\mathbb{R}\ f(3,z)=g(4). >\] and we chose the name \(z_1\) for this value that exists. > >We called it \(z_1\) rather than \(z\) because we immediately doing the same thing again with \(x := 9\) and \(y := 7\) to get >\[ > \exists z{\in}\mathbb{R}\ f(9,z)=g(7), >\] >and we can’t use the name for the \(z\) for both numbers known to exist (since there’s no reason to believe they’ll be equal). > >— > Proof: Assume \(\exists z\in\mathbb{R}\ \forall x\in\mathbb{R}\ \forall y{\in}\mathbb{R}\ \ f(x,z)=g(y)\) . (Note: the order of quantifiers has changed!) Then there exists \(z{\in}\mathbb{R}\) such that \(f(3,z) = g(4)\) and \(f(9, z) = g(7)\). ⋮ > >Note: Because we always handle quantifiers in order, we first give a name to the value \(z\) such that >\[ >\forall x\in\mathbb{R}\ \forall z{\in}\mathbb{R}\ f(3,z)=g(y). >\] >We can then plug 3 and 4 into this, and also plug in 9 and 7, and know it is the same \(z\) for both.
Previous: 3.4 Proving Implications
Next: 3.6 Asymptotic Analysis